In [12]:
using PyCall
@pyimport IPython.display as ipdisplay

In [2]:
# example comparison function
function compare_numbers(a,b)
    if a[1] < b[1]
        return -1
    elseif a[1] > b[1]
        return 1
    else
        return 0
    end
end

# example comparison function
function compare_L2(a,b)
    if norm(a,2) < norm(b,2)
        return -1
    elseif norm(a,2) > norm(b,2)
        return 1
    else
        return 0
    end
end

# example comparison function
function compare_L1(a,b)
    if norm(a,1) < norm(b,1)
        return -1
    elseif norm(a,1) > norm(b,1)
        return 1
    else
        return 0
    end
end


Out[2]:
compare_L1 (generic function with 1 method)

In [3]:
# insertion sort
# Runtime: O(n^2)
function insertion_sort(A,compare)
    n = size(A,1)
    for i=2:n
        val = A[i,:]
        ind = 0
        for j=1:i-1 #TODO use binary search instead
            if compare(val,A[j,:]) <= 0
                ind = j
                break
            end 
        end
        if ind > 0
            A[ind+1:i,:] = A[ind:i-1,:]
            A[ind,:] = val
        end
    end
    A
end


Out[3]:
insertion_sort (generic function with 1 method)

In [25]:
function tostring(a)
    s = @sprintf("%d",a[1])
    for n in a[2:end]
        s = @sprintf("%s, %d",s, n)
    end
    s
end


Out[25]:
tostring (generic function with 1 method)

In [24]:
# simple test
n = 10
test1 = int(rand(n) * 100)
println(test1)
test1_sorted = insertion_sort(test1,compare_numbers)
println(test1_sorted)
# duplicates
test2 = [test1; test1]
println(test2)
test2_sorted = insertion_sort(test2,compare_numbers)
println(test2_sorted)
# vector test
println("2d vecs:")
vtest1 = int(rand(n,2)*100)
for i=1:n
    println(vtest1[i,:], "(" , norm(vtest1[i,:],2), ")")
end
println("L2:")
vtest1_sorted = insertion_sort(vtest1,compare_L2)
for i=1:n
    println(vtest1_sorted[i,:], "(" , norm(vtest1_sorted[i,:],2), ")")
end
println("L1:")
vtest1_sorted_alt = insertion_sort(vtest1,compare_L1)
for i=1:n
    println(vtest1_sorted_alt[i,:], "(" , norm(vtest1_sorted_alt[i,:],2), ")")
end


[44,32,65,98,6,59,98,8,29,99]
[6,8,29,32,44,59,65,98,98,99]
[6,8,29,32,44,59,65,98,98,99,6,8,29,32,44,59,65,98,98,99]
[6,6,8,8,29,29,32,32,44,44,59,59,65,65,98,98,98,98,99,99]
2d vecs:
[78 72](106.1508360777248)
[20 23](30.479501308256342)
[3 55](55.08175741568164)
[18 90](91.78235124467014)
[39 56](68.24221567329126)
[60 1](60.00833275471)
[14 73](74.33034373659254)
[96 36](102.52804494381036)
[25 68](72.44998274671981)
[40 49](63.25345840347387)
L2:
[20 23](30.479501308256342)
[3 55](55.08175741568164)
[60 1](60.00833275471)
[40 49](63.25345840347387)
[39 56](68.24221567329126)
[25 68](72.44998274671981)
[14 73](74.33034373659254)
[18 90](91.78235124467014)
[96 36](102.52804494381036)
[78 72](106.1508360777248)
L1:
[20 23](30.479501308256342)
[40 49](63.25345840347387)
[3 55](55.08175741568164)
[39 56](68.24221567329126)
[60 1](60.00833275471)
[25 68](72.44998274671981)
[14 73](74.33034373659254)
[78 72](106.1508360777248)
[18 90](91.78235124467014)
[96 36](102.52804494381036)

In [26]:
ipdisplay.HTML(@sprintf("<h2>%s</h2>",tostring(test2_sorted)))


Out[26]:

6, 6, 8, 8, 29, 29, 32, 32, 44, 44, 59, 59, 65, 65, 98, 98, 98, 98, 99, 99

loop invariants:

  • used to show an algorithm is correct, similar to proof by induction, but instead of doing to infinity we only go to the end of the loop

invariant: some claim that should be true at the before the first iteration, at beginning of each iteration, and at the end of the algorithm

initialization: is the invariant true prior to the first iteration?

maintenance: if it is true before an iteration fo the loop, it remains true before the next iteration

termination: when the loop terminates, the invariant gives us a useful property that helps show the algorithm is correct

loop invariants for insertion sort:

invariant:_ At the start of each iteration the subarray $A[1 \ldots j-1]$ consists of the elements originally in $A[1 \ldots j-1]$ but in sorted order

initialization: $A[1 \ldots j-1] = A[1]$ which consists of the original $A[1]$ and is in sorted order.

maintenance: informally, during an iteration the elements $A[1 \ldots j]$ are put in order by inserting the original element $A[j]$ into the appropiate locatoin within the sorted elements $A[1 \ldots j-1]$, so that at the beginning of the next iteration ($j = j+1$), the invariant holds.

termination: the loop terminates when $j = n+1$, so that $A[1 \ldots j-1] = A[1 \ldots n]$, which is the entire array sorted. Hence the entire array is sorted and the algorithm is correct.

Analysis